using System;
using System.Collections.Generic;
using System.Text;


namespace sort
{
    class sorter
    {
        public static void Native(int[] Arr)
        {
            Array.Sort<int>(Arr);
        }
        private static void swap(ref int a, ref int b)
        {
            int tmp = a;
            a = b;
            b = tmp;
        }
        public static void Insertion(int[] Arr)
        {
            Insertion(Arr, 0, Arr.Length -1);
            /*
            for (int i = 0; i < Arr.Length; i++)
            {
//                if (i == 9156)
//                    Console.Write("break");
                for (int j = i; j > 0; j--)
                {
                    if (Arr[j] < Arr[j - 1]) swap(ref Arr[j], ref Arr[j - 1]);
                    else break;
                }

            }*/
        }
        public static void Insertion(int[] Arr, int a, int b)
        {

            for (int i = a; i <= b; i++)
            {
                for (int j = i; j > a; j--)
                {
                    if (Arr[j] < Arr[j - 1]) swap(ref Arr[j], ref Arr[j - 1]);
                    else break;
                }

            }
        }
        public static int part(int[] A, int a, int b, int val)
        {
            while (true)
            {
                for (; (A[a] <= val) && (a < b); a++) ;
                for (; (A[b] >= val) && (a < b); b--) ;
                if (a < b) swap(ref A[a], ref A[b]);
                else break;
            }
            return b;
        }
        public static int part2(int[] A, int start, int end, int val)
        {
            while (true)
            {
                start++;
                end--;
                while (start < end) 
                {
                    if (A[start] > val) break;
                    if (A[++start] > val) break;
                    start++;
                }
                while (start < end)
                {
                    if (A[end] < val) break;
                    if (A[--end] < val) break;
                    --end;
                }
                if (start < end) swap(ref A[start], ref A[end]);
                else break;
            }
 //           if(A[a]<A[b])swap(ref A[a], ref A[b]);
            return end;
        }

        public static void tsort(int[] A, int a, int c, int b)
        {
            if (A[a] > A[b]) swap(ref A[a], ref A[b]);
            if (A[c] < A[a]) swap(ref A[c], ref A[a]);
            else if (A[c] > A[b]) swap(ref A[c], ref A[b]);
        }
        static  void tsort2(int[] A, int a, int c, int b)
        {
            if (A[a] > A[b]) swap(ref A[a], ref A[b]);
            if (A[c] < A[a]) swap(ref A[c], ref A[a]);
            else if (A[c] > A[b]) swap(ref A[c], ref A[b]);
        }
        public static void QuickRek(int[] A, int a, int b)
        {
            if (b - a < 24) { Insertion(A, a, b); return; }
            int c = (a + b) / 2;
            tsort(A, a, c, b);
            int p = part(A, a, b, A[c]);
            QuickRek(A, a, p - 1);
            QuickRek(A, p, b);
        }
        public static void Quick(int[] Arr)
        {

            QuickRek(Arr, 0, Arr.Length - 1);
            //algInd2(ref Arr, 0, Arr.Length - 1);
        }

        public static void QuickRek2(int[] A, int a, int b)
        {
            if (b - a < 24) { Insertion(A, a, b); return; }
            int c = (a + b) / 2;
            tsort(A, a, c, b);
            int start = a;
            int end = b;

            int val = A[c];

            while (true)
            {
                start++;
                end--;
                while (start < end)
                {
                    if (A[start] > val) break;
                    if (A[++start] > val) break;
                    start++;
                }
                while (start < end)
                {
                    if (A[end] < val) break;
                    if (A[--end] < val) break;
                    --end;
                }
                if (start < end) swap(ref A[start], ref A[end]);
                else break;
            }
            if (start != end) if (A[start] < A[end]) swap(ref A[start], ref A[end]);
            QuickRek2(A, a, end);
            QuickRek2(A, start, b);
        }
        public static void Quick2(int[] Arr)
        {
                QuickRek2(Arr, 0, Arr.Length - 1);

                //algInd2(ref Arr, 0, Arr.Length - 1);
        }

        public static void QuickRek3(int[] A, int a, int b)
        {
            while(b-a>24)
            {
                int c = (a + b) / 2;
                tsort(A, a, c, b);
                int be = a;
                int en = b;
                int val = A[c];
                en--; be++;
                do
                {
                    for (; A[be] < val; be++) ;
                    for (; A[en] > val; en--) ;
                    if (be < en) swap(ref A[be], ref A[en]);
                    else if (be > en) break;
                    en--; be++;
                } while (be <= en);
                if (b - be >= en - a)
                {
                    QuickRek3(A, a, en);
                    a = be;
                }
                else
                {
                    QuickRek3(A, be, b);
                    b = en;
                }
            }
            Insertion(A, a, b);
        }
        public static void Quick3(int[] Arr)
        {
            QuickRek3(Arr, 0, Arr.Length - 1);
            //algInd2(ref Arr, 0, Arr.Length - 1);
        }


        public static void QuickRek3a(int[] A, int a, int b)
        {
            while (b - a > 24)
            {
                int c = (a + b) / 2;
                tsort(A, a, c, b);
                int be = a;
                int en = b;
                int val = A[c];
                en--; be++;
                do
                {
                    for (; A[be] < val; be++) ;
                    for (; A[en] > val; en--) ;
                    if (be < en) swap(ref A[be], ref A[en]);
                    else if (be > en) break;
                    en--; be++;
                } while (be <= en);
                    QuickRek3(A, a, en);
                    a = be;
     
            }
            Insertion(A, a, b);
        }
        public static void Quick3a(int[] Arr)
        {
            QuickRek3a(Arr, 0, Arr.Length - 1);
            //algInd2(ref Arr, 0, Arr.Length - 1);
        }


        public static void QuickRek4(int[] A, int a, int b)
        {
            if (b - a < 16) {  return; }//!!!!
            int c = (a + b) / 2;
            if (A[a] > A[b]) swap(ref A[a], ref A[b]);
            if (A[c] < A[a]) swap(ref A[c], ref A[a]);
            else if (A[c] > A[b]) swap(ref A[c], ref A[b]);
            int p = part(A, a, b, A[c]);
            QuickRek4(A, a, p - 1);
            QuickRek4(A, p, b);
        }

        public static void Quick4(int[] Arr)
        {
            QuickRek4(Arr, 0, Arr.Length - 1);
            Insertion(Arr);
        }
        public static void QuickRek4a(int[] A, int a, int b)
        {
            if (b - a < 24) { return; }//!!!!
            int c = (a + b) / 2;
            if (A[a] > A[b]) swap(ref A[a], ref A[b]);
            if (A[c] < A[a]) swap(ref A[c], ref A[a]);
            else if (A[c] > A[b]) swap(ref A[c], ref A[b]);
            int p = part(A, a, b, A[c]);
            QuickRek4(A, a, p - 1);
            QuickRek4(A, p, b);
        }
        public static void Quick4a(int[] Arr)
        {
            QuickRek4a(Arr, 0, Arr.Length - 1);
            Insertion(Arr);
        }
        static void myInsertion(int[] Arr,int a,int b)
        {
            b++;
            for (int i = 7; i < b; i++)
            {
                for (int j = i; j > 6; j-=7)
                {
                    if (Arr[j] < Arr[j -7]) swap(ref Arr[j], ref Arr[j -7]);
                    else break;
                }
            }
            for (int i = 3; i < b; i++)
            {
                for (int j = i; j > 2; j-=3)
                {
                    if (Arr[j] < Arr[j - 3]) swap(ref Arr[j], ref Arr[j - 3]);
                    else break;
                }
            }
            for (int i = 1; i < b; i++)
            {
                for (int j = i; j > 0; j--)
                {
                    if (Arr[j] < Arr[j - 1]) swap(ref Arr[j], ref Arr[j - 1]);
                    else break;
                }
            }
        }
  
        public static void myInsertion(int[] Arr)
        {
            myInsertion(Arr, 0, Arr.Length -1);
        }

        static int new_gap(int gap)
        {
            gap = (gap * 10) / 13;
            if (gap == 9 || gap == 10)
                return 11;
            if (gap < 1)
                return 1;
            return gap;
        }

        static void combsort(int[] array, int start, int size)
        {
            size -= start;

            int gap = ++size;
            while (true)
            {
                gap = new_gap(gap);
                bool swapped = false;
                int end = start + size - gap;
                for (int i = start; i < end; i++)
                {
                    int j = i + gap;
                    if (array[i] > array[j])
                    {
                        int val = array[i];
                        array[i] = array[j];
                        array[j] = val;
                        swapped = true;
                        
                    }
                }
                if (gap == 1 && !swapped)
                    break;
            }
        }
        public static void combsort(int[] array)
        {
            combsort(array, 0, array.Length - 1);
        }

    }


    public class qsort {
        int tre;
        public qsort(int a) { tre = a; }
        public  void QuickRek2v(int[] A, int a, int b)
        {
            if (b - a < tre) { sorter.Insertion(A, a, b); return; }//!!!!
            int c = (a + b) / 2;
            sorter.tsort(A, a, c, b);
            int p = sorter.part(A, a, b, A[c]);
            QuickRek2v(A, a, p - 1);
            QuickRek2v(A, p, b);
        }
        public  void Quick2v(int[] Arr)
        {
            QuickRek2v(Arr, 0, Arr.Length - 1);
            //algInd2(ref Arr, 0, Arr.Length - 1);
        }
    }
}



